package dualpointer;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.Map;

public class D230828 {
    // 最长无重复子数组


    // 遍历数组, 使用哈希表记录 元素值 和 下标
    // 当出现重复的元素, 更新最大值, 删除重复元素和下标在重复元素之前的元素
    // 时间：O(N2)
    // 空间：O(N)
    public int maxLength (int[] arr) {
        int res = 0;
        // 哈希表, Key 为 值, value 为数组中的 下标
        HashMap<Integer, Integer> list = new HashMap<>();
        for (int i = 0; i < arr.length; i++) {
            if (list.containsKey(arr[i])) {
                // 出现重复元素, 先更新最大值
                res = Math.max(res, list.size());

                // 获取重复元素的下标
                int j = list.get(arr[i]);
                // 将重复元素和下标在重复元素之前的元素 移出哈希表
                // 遍历哈希表, 对比下标, 记录要删除的元素
                ArrayList<Integer> tmp = new ArrayList<>();
                for (Map.Entry<Integer, Integer> entry: list.entrySet()) {
                    if (entry.getValue() <= j) {
                        tmp.add(entry.getKey());
                    }
                }
                // 删除
                for (Integer key : tmp) {
                    list.remove(key);
                }
            }
            // 加入哈希表
            list.put(arr[i], i);
        }
        res = Math.max(res, list.size());
        return res;
    }

    // 使用一个哈希表，统计数组中元素出现的次数
    // 滑动窗口遍历数组
    // 右边窗口先移动，元素进入哈希表，统计出现次数
    // 一旦有出现次数大于 1 的元素，就需要移动左边窗口，同时减去元素出现的次数，直到次数不大于 1
    // 时间：O(N)
    // 空间：O(N)
    public int maxLength2 (int[] arr) {
        //哈希表记录窗口内非重复的数字
        HashMap<Integer, Integer> mp = new HashMap<>();
        int res = 0;
        //设置窗口左右边界
        for(int left = 0, right = 0; right < arr.length; right++){
            // 窗口右移, 进入哈希表统计元素出现次数
            mp.put(arr[right], mp.getOrDefault(arr[right], 0) + 1);

            // 出现次数大于 1，则窗口内有重复
            while(mp.get(arr[right]) > 1)
                // 窗口左移，同时减去该数字的出现次数
                mp.put(arr[left], mp.get(arr[left++])-1);
            // 维护无重复子数组长度最大值
            res = Math.max(res, right - left + 1);
        }
        return res;
    }
}
